/***************************************************
 * 此文件的版权归属xxxx公司所有，未经允许，请勿复制
 */
package com.leetcode;

/************************************************
 * @author yejf
 * @since JDK7.0
 * @CreateDate 2020年4月20日 下午1:46:04 
 * @description 此类用来描述了深度优先遍历算法[Deep First Search]
 *
 */

public class DFS_Algorithm {
	
	final char ISLAND = '1';
	final char OCEAN = '0';
	/** 代表遍历过的节点*/
	final char FLAG = '2';
	
	/************
	 	计算岛屿的面积:
	 	给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
		岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
		此外，你可以假设该网格的四条边均被水包围。
		示例 1:
		输入:
		11110
		11010
		11000
		00000
		输出: 10
		示例 2:
		输入:
		11000
		11000
		00100
		00011
		输出: 7
		解释: 每座岛屿只能由水平和/或竖直方向上相邻的陆地连接而成。
	 * @param grid
	 */	
	public int islandsArea(char[][] grid) {
		//
		int count = 0;
		//循环
		for (int row = 0; row < grid.length; row++) {
			//
			for(int col = 0;col < grid[row].length;col++) {
				//判断
				if(grid[row][col] == ISLAND) {
					//根据DFS算法，找出这个节点上下左右的位置是否符合要求
					int a = areaDFS(grid, row, col);
					count = Math.max(count, a);
				}
			}
		}
		//
		return count;
	}
	/****
	 * DFS算法, 计算岛屿的面积，依次根据当前节点位置处的上下左右 4个位置,以当前位置 row, col 为准
	 * 上： row-1, col
	 * 下： row+1, col
	 * 左： row, col-1
	 * 右: row, col+1
	 * @param grid
	 * @param row
	 * @param col
	 * @return
	 */
	private int areaDFS(char[][] grid, int row, int col) {
		//判断是否处在区域之中[没有越界]
		if(!inArea(grid,row,col)) {
			return 0;
		}
		//如果这个值不再是1，则返回0
		if(grid[row][col] != ISLAND) {
			return 0;
		}
		//把遍历过的节点[元素] 修改为2，这样 '1'还是代表岛屿,'0'还是代表海洋，'2'就代表已经检查过的节点
		grid[row][col] = FLAG;
		//递归调用
		return 1 + 
				areaDFS(grid, row-1, col)+   //当前节点的上面
				areaDFS(grid, row+1, col)+		//当前节点的下面
				areaDFS(grid, row, col-1)+		//当前节点的左边
				areaDFS(grid, row, col+1);		//当前节点的右边
	}
	
	/************
 	计算岛屿的个数:
 	给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
	岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
	此外，你可以假设该网格的四条边均被水包围。
	示例 1:
	输入:
	11110
	11010
	11000
	00000
	输出: 1
	示例 2:
	输入:
	11000
	11000
	00100
	00011
	输出: 3
	解释: 每座岛屿只能由水平和/或竖直方向上相邻的陆地连接而成。
 * @param grid
 */	
	public int numIsland(char[][] grid) {
		//参数判断
		if(grid == null || grid.length == 0) {
			return 0;
		}
		//定义变量来收收大小
		int nums = 0;
		//循环判断
		for(int row = 0; row < grid.length; row++) {
			//内层循环
			for(int col=0; col < grid[row].length; col++) {
				//如果节点是 ISLAND的话，启动深度优先搜索
				if(grid[row][col] == ISLAND) {
					++nums; //计数1次
					//深度优化搜索
					numDFS(grid, row, col);
				}
			}
		}
		//
		return nums;
	}
	/****
	 * 求岛屿个数的深度优先
	 * @param grid
	 * @param row
	 * @param col
	 */
	private void numDFS(char[][] grid, int row, int col) {
		//判断是否超过边界
		if(!inArea(grid, row, col)) {
			return;
		}
		//判断是否是海洋或者是访问过的节点
		if(grid[row][col] == OCEAN || grid[row][col] == FLAG) {
			return ;
		}
		//把访问过的节点值改为 FLAG
		grid[row][col] = FLAG;
		//递归调用
		numDFS(grid, row-1, col); //递归上面的节点
		numDFS(grid, row+1, col); //递归下面的节点
		numDFS(grid, row, col-1); //递归左边的节点
		numDFS(grid, row, col+1); //递归右边的节点
	}
	/****
	 * 判断row和col是否还处在整个节点的边界之中
	 * @param grid
	 * @param row
	 * @param col
	 * @return
	 */
	private boolean inArea(char[][] grid, int row, int col) {
		return 0 <= row && row < grid.length
					&& 0 <= col && col < grid[0].length;
	}
	
	public static void main(String[] args) {
		DFS_Algorithm dfs = new DFS_Algorithm();
		char[][] grid1 = new char[][] {
			{'1','1','1','1','0'},
			{'1','1','0','1','1'},
			{'1','1','0','0','0'},
			{'0','0','0','0','0'},
		};
		char[][] grid2 = new char[][] {
			{'1','1','0','0','0'},
			{'1','1','0','0','0'},
			{'0','0','1','0','0'},
			{'0','0','0','1','1'},
		};
		System.out.println("岛屿的面积："+dfs.islandsArea(grid1));
		System.out.println("岛屿的个数："+dfs.numIsland(grid2));
	}
}
